这道题是一道典型的搜索题,我们用表示蜗牛在这个点,走了步,当前的方向(起点的,特殊处理一下)。
当蜗牛确定一个方向后,我们就不断让它前进,同时记录它走过的格子,直到它遇到障碍,出界或者到达已走过的点停止。
如果蜗牛遇到障碍,我们就枚举每个方向,因为前方有障碍,后方已经走过,所以蜗牛只会向左或向右转,不需要特殊处理。
代码中的作用是找到后面的单词,使之跳过一些语句,感觉作用比,强,可以减少一些判断。
最后是代码:
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 120;
char x;
int n,m,y,Ans;
char Map[ MAXN + 5 ][ MAXN + 5 ];
bool vis[ MAXN + 5 ][ MAXN + 5 ];
int tx[ 5 ] = { 0 , 1 , -1 , 0 , 0 };
int ty[ 5 ] = { 0 , 0 , 0 , 1 , -1 };
void dfs( int x , int y , int step , int s ) {
Ans = max( Ans , step );
if( s ) {
int fx = x + tx[ s ] , fy = y + ty[ s ];
if( fx == 0 || fy == 0 || fx == n + 1 || fy == n + 1 || Map[ fx ][ fy ] == '#' )
goto there;
if( vis[ fx ][ fy ] )
return;
vis[ fx ][ fy ] = 1;
dfs( fx , fy , step + 1 , s );
vis[ fx ][ fy ] = 0;
return;
}
there:;
for( int i = 1 ; i <= 4 ; i ++ ) {
int fx = x + tx[ i ] , fy = y + ty[ i ];
if( fx == 0 || fy == 0 || fx == n + 1 || fy == n + 1 || Map[ fx ][ fy ] == '#' || vis[ fx ][ fy ] )
continue;
vis[ fx ][ fy ] = 1;
dfs( fx , fy , step + 1 , i );
vis[ fx ][ fy ] = 0;
}
}
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
Map[ i ][ j ] = '.';
for( int i = 1 ; i <= m ; i ++ ) {
cin >> x;
scanf("%d",&y);
Map[ y ][ x - 'A' + 1 ] = '#';
}
/*for( int i = 1 ; i <= n ; i ++ ) {
for( int j = 1 ; j <= n ; j ++ )
printf("%c",Map[ i ][ j ]);
printf("\n");
}*/
vis[ 1 ][ 1 ] = 1;
dfs( 1 , 1 , 1 , 0 );
printf("%d",Ans);
return 0;
}